# source:https://leetcode.cn/problems/smallest-difference-lcci/ 双指针
from functools import cache


class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        ans = inf
        i, j = 0, 0
        for _ in range(len(a)+len(b)):
            if i >= len(a) or j >= len(b):
                break
            ans = min(ans, abs(a[i]-b[j]))
            if a[i] <= b[j]:
                i += 1
            else:
                j += 1
        return ans

# source:https://leetcode.cn/problems/count-the-number-of-incremovable-subarrays-ii/submissions/594976764/  双指针 后缀 分析情况
class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        ans = 0
        while i < n-1 and nums[i] < nums[i+1]:
            i += 1
        ans += i + 2
        if i == n-1:
            return n*(n+1)//2
        j = n-1
        while j == n-1 or nums[j] < nums[j+1]:
            while i >= 0 and nums[i] >= nums[j]:
                i -= 1
            ans += i + 2
            j -= 1
        return ans

# source:https://leetcode.cn/problems/maximum-points-after-collecting-coins-from-all-nodes/ 记忆化搜索
class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        g = [[] for _ in range(len(edges)+1)]
        for i, j in edges:
            g[i].append(j)
            g[j].append(i)

        @cache
        def dfs(i, j, fa):
            res1 = (coins[i] >> j) - k
            res2 = coins[i] >> (j+1)
            for v in g[i]:
                if v != fa:
                    res1 += dfs(v, j, i)
                    if j < 14:
                        res2 += dfs(v, j+1, i)
            return max(res1, res2)
        return dfs(0, 0, -1)

# 树形DP
